Tidak terjejas dengan kekurangan hasil Almeida, pada April 1508, Raja Manuel memutuskan untuk menghantar sebuah armada terus ke Melaka, terdiri dari empat kapal di bawah komando Diogo Lopes de Sequeira, yang juga ditugaskan untuk membawa Madagascar dan mengumpulkan maklumat tentang orang Cina. Sequeira menerima perintah diraja dengan khusus mengarahkan beliau untuk mendapatkan kebenaran untuk membuka pos perdagangan dan perdagangan secara diplomatik, bukan untuk bertindak balas kepada sebarang provokasi dan bukan untuk membakar kecuali melepaskan tembakan.[17]

Pada April 1509, armada itu berada di Cochin dan Viceroy, Dom Francisco de Almeida, menggabungkan satu lagi karak di dalam armada untuk menguatkannya. Keputusan itu tidak sepenuhnya tidak bersalah, ketika melancarkan beberapa penyokong pesaing politik Almeida, Afonso de Albuquerque. Antara krewnya juga termasuk Ferdinand Magellan.[18]

Ekspedisi tiba di Melaka pada September 1509 dan De Sequeira segera menghubungi peniaga Cina di pelabuhan itu, yang kemudiannya menjemputnya di salah satu kapal dagang mereka dan menerimanya dengan baik untuk makan malam dan mengadakan pertemuan dengan Sultan Mahmud. Sultan segera memberikan kebenaran Portugis untuk menubuhkan feitoria dan menyediakan bangunan kosong untuk tujuan tersebut. Waspada dengan ancaman bahawa Portugis menimbulkan minat mereka, bagaimanapun, komuniti pedagang kuat Gujarati Muslim dan Jawa meyakinkan Sultan Mahmud dan Bendahara untuk mengkhianati dan menangkap Portugis.[19]

De Sequeira begitu yakin dengan kebolehan Sultan bahawa beliau mengabaikan maklumat yang Duarte Fernandes, seorang Kristian Baru yang fasih berbahasa Parsi, yang diperolehi dari penjaga perengaian kata tentang persiapan yang sedang berlangsung untuk memusnahkan armada, yang disahkan oleh pedagang Cina.[20] Beliau sedang bermain catur di atas perdana kapalnya ketika armada Tanah Melayu, menyamar sebagai peniaga, menyerang kapal Portugis.[21] Orang Portugis menolak setiap percubaan menaiki kapal, tetapi berhadapan dengan banyak kapal Tanah Melayu dan tidak mampu menduduki mana-mana pasukan untuk menyelamatkan orang Portugis yang tinggal di feitoria, de Sequeira memutuskan untuk kembali ke India sebelum monsun bermula dan meninggalkan mereka yang terkandas di Asia Tenggara. Sebelum berangkat, beliau menghantar pesanan kepada Sultan dan bendahara dalam bentuk dua tawanan masing-masing dengan anak panah melalui tengkorak mereka sebagai saksi terhadap apa yang akan terjadi kepada mereka jika terdapat kemudaratan yang datang kepada 20 orang yang ditinggalkan oleh Portugis, yang menyerah diri.[21]